package com.Algorithm.Study.ThinkTest;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/09/6:29
 * @Description:
 * @Target:
 */
public class HeapSort {
    // 先写一个Heapify,即去掉大根堆根(最大值)节点时,怎么判断下一个大根节点

    // 此时已经将heapsize末尾的整到根节点了,选取领袖,需要入参,数组,当前索引,以及heapsize
    public void heapify(int arr[],int index,int heapsize){

        int left = 2*index+1;   // 左孩子的计算

        while (left<heapsize){    // 判断有没有孩子,有右必有左,所以判断左就好了
        // 两个孩子谁更大,先判断有没有左孩子,再判断左右孩子谁大(没右孩子,就左孩子大呗,,)
        int largest = left+1<heapsize&&arr[left+1]>arr[left]?left+1:left;

        // 父亲和孩子比,哪个大
            largest = arr[index]>arr[largest]?index:largest;
            if(largest==index){
                break;
            }

            // 如果不是index最大,那么就要换索引了
            swap(arr,index,largest);   // 换值
            index = largest;   // 换索引
            left = 2*index+1;  // 下一个左孩子.注意while是一直执行的..
        }

    }



    public void swap(int arr[],int a,int b){
        int m = arr[a];
        arr[a] = arr[b];
        arr[b] = arr[a];
    }




}

